package oj;

/**
 * 根据前序和中序遍历结果，还原二叉树
 *
 */
public class Num105 {
    //当前处理到前序遍历的哪个位置
    int index=0;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeInternal(preorder,inorder,0,inorder.length);
    }

    /**
     * 根据传入的前序遍历和中序遍历的部分区间构建一颗二叉树，并返回根节点
     * [left,right) 当前前序遍历的根节点对应到中序遍历的区间
     * @param preorder 前序遍历结果
     * @param inorder 中序遍历结果
     * @param left
     * @param right
     * @return
     */
    public TreeNode buildTreeInternal(int[] preorder,int[] inorder,int left,int right){
        if(left>=right){
            return null;
        }
        if(index>=preorder.length){
            return null;
        }
        //此时前序遍历结果中还有没处理的元素，从index位置取得一个元素构建根节点
        TreeNode root=new TreeNode(preorder[index]);
        index++;
        //处理左树
        //拿着root.val去中序遍历中找到该值对应的索引pos
       int pos=find(inorder,left,right,root.val);
       root.left=buildTreeInternal(preorder,inorder,left,pos);
       root.right=buildTreeInternal(preorder,inorder,pos+1,right);
        return root;
    }

    private int find(int[] inorder, int left, int right, int val) {
        for (int i = left; i <right ; i++) {
            if(val==inorder[i]){
                return i;
        }
    }
        return -1;
}
}

